import java.util.ArrayList;
import java.util.Stack;
/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-30
 * Time: 11:08
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
/**
 * @author 86189
 */
public class Solution2 {
    public int[] preorderTraversal (TreeNode root) {
        //非递归，也就是使用迭代的方法，需要借助栈的思想
        Stack<TreeNode> stack=new Stack<>();
        ArrayList<Integer> list=new ArrayList<>();
        if(root==null){
            return new int[0];
        }
        stack.push(root);
        while ( !stack.isEmpty() ){
            TreeNode cur=stack.pop();
            list.add(cur.val);
            if(cur.right!=null){
                stack.push( cur.right );
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
        int[] ret=new int[list.size()];
        for(int i=0;i < list.size(); i++){
            ret[i]=list.get(i);
        }
        return ret;
       
    }
}
